package org.nowcoder.huawei.c100;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 1:生成哈夫曼树
 */
public class HC001 {

    static class BTree {
        private int weight;
        private BTree left;
        private BTree right;

        public BTree(int weight) {
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        solve(new int[]{5, 15, 40, 30, 10});
    }

    public static void inOrder(BTree root) {
        if (root != null) {
            inOrder(root.left);
            System.out.print(root.weight + " ");
            inOrder(root.right);
        }
    }

    public static void solve(int[] weights) {
        PriorityQueue<BTree> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
        for (int weight : weights) {
            minHeap.add(new BTree(weight));
        }

        while (minHeap.size() > 1) {
            BTree l = minHeap.poll();
            BTree r = minHeap.poll();
            BTree newNode = new BTree(l.weight + r.weight);
            newNode.left = l;
            newNode.right = r;
            minHeap.add(newNode);
        }
        BTree root = minHeap.peek();
        inOrder(root);
    }
}
